백준 11779번
오늘 풀어본 문제는 백준의 11779번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
$n$ $(1 \le n \le 1000)$ 개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 $m$ $(1 \le m \le 100000)$ 개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.
입력
첫째 줄에 도시의 개수 $n$ $(1 \le n \le 1000)$ 이 주어지고 둘째 줄에는 버스의 개수 $m$ $(1 \le m \le 100000)$ 이 주어진다. 그리고 셋째 줄부터 $m+2$ 줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 $0$ 보다 크거나 같고, $100000$ 보다 작은 정수이다.
그리고 $m+3$ 째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.
출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.
셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.
풀이과정
1번째 시도
문제를 보고 다익스트라 알고리즘을 활용해야 한다는 것을 알 수 있었다. 그런데 마지막에 출력할 때 경로를 추적하는 부분도 포함되어 있어 이전 정점의 번호도 저장하는 방식으로 구현해야 한다는 것을 알 수 있었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
struct compare{
bool operator()(const pair<int, int> a, const pair<int, int> b){
return a.second > b.second;
}
};
int graph[1001][1001];
pair<int, int> table[1001];
void dijkstra(int n, int departure, int arrival);
void retrace(int departure, int arrival);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, departure, arrival;
cin >> n >> m;
for (int i=1; i<n+1; i++) {
for (int j=1; j<n+1; j++) {
graph[i][j] = -1;
}
}
for (int i=0; i<m; i++) {
int start, end, weight;
cin >> start >> end >> weight;
graph[start][end] = weight;
}
cin >> departure >> arrival;
dijkstra(n, departure, arrival);
cout << table[arrival].first << "\n";
retrace(departure, arrival);
return 0;
}
void dijkstra(int n, int departure, int arrival) {
bool visit[1001] = {false,};
for (int i=1; i<n+1; i++) {
table[i].first = INT_MAX;
if (i == departure) table[i].first = 0;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
pq.emplace(departure, 0);
for (int i=0; i<n-1; i++) {
pair<int, int> curr = pq.top();
pq.pop();
while (visit[curr.first] || curr.first == arrival) {
curr = pq.top();
pq.pop();
}
visit[curr.first] = true;
if (curr.second == INT_MAX) continue;
for (int j=1; j < n + 1; j++) {
if (graph[curr.first][j] >= 0) {
if (curr.second + graph[curr.first][j] < table[j].first) {
table[j].first = curr.second + graph[curr.first][j];
table[j].second = curr.first;
pq.emplace(j, table[j].first);
}
}
}
}
}
void retrace(int departure, int arrival) {
int curr = arrival;
stack<int> s;
while (curr != departure) {
s.push(curr);
curr = table[curr].second;
}
s.push(curr);
cout << s.size() << "\n";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
}
실행 결과 ‘틀렸습니다’ 가 나왔다.
2번째 시도
질문 게시판 등을 떠돌며 문제점을 찾아본 결과, 입력으로 한 정점 쌍에 여러 개의 간선이 올 수 있다는 것을 알게 되었다. 그래서 가장 짧은 간선만을 저장하고 다익스트라 알고리즘을 실행하게 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
struct compare{
bool operator()(const pair<int, int> a, const pair<int, int> b){
return a.second > b.second;
}
};
int graph[1001][1001];
pair<int, int> table[1001];
void dijkstra(int n, int departure, int arrival);
void retrace(int departure, int arrival);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, departure, arrival;
cin >> n >> m;
for (int i=1; i<n+1; i++) {
for (int j=1; j<n+1; j++) {
graph[i][j] = -1;
}
}
for (int i=0; i<m; i++) {
int start, end, weight;
cin >> start >> end >> weight;
if (graph[start][end] != -1) {
graph[start][end] = min(graph[start][end], weight);
}
else {
graph[start][end] = weight;
}
}
cin >> departure >> arrival;
dijkstra(n, departure, arrival);
cout << table[arrival].first << "\n";
retrace(departure, arrival);
return 0;
}
void dijkstra(int n, int departure, int arrival) {
bool visit[1001] = {false,};
for (int i=1; i<n+1; i++) {
table[i].first = INT_MAX;
if (i == departure) table[i].first = 0;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
pq.emplace(departure, 0);
for (int i=0; i<n-1; i++) {
pair<int, int> curr = pq.top();
pq.pop();
while (visit[curr.first] || curr.first == arrival) {
curr = pq.top();
pq.pop();
}
visit[curr.first] = true;
if (curr.second == INT_MAX) continue;
for (int j=1; j < n + 1; j++) {
if (graph[curr.first][j] >= 0) {
if (curr.second + graph[curr.first][j] < table[j].first) {
table[j].first = curr.second + graph[curr.first][j];
table[j].second = curr.first;
pq.emplace(j, table[j].first);
}
}
}
}
}
void retrace(int departure, int arrival) {
int curr = arrival;
stack<int> s;
while (curr != departure) {
s.push(curr);
curr = table[curr].second;
}
s.push(curr);
cout << s.size() << "\n";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
}
실행 결과 ‘시간 초과’ 가 나왔다.
5번째 시도
시간 초과 문제를 해결하기 위해 여러 가지 방법을 시도해보았고, 최종적으로 성공한 방식은 현재 확인하는 정점까지의 거리가 최단 거리보다 크면 생략하고, graph 의 자료형을 vector<unordered_map<int, int>> 으로 설정하는 방식이었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
struct compare{
bool operator()(const pair<int, int> a, const pair<int, int> b){
return a.second > b.second;
}
};
vector<unordered_map<int, int>> graph(1001);
pair<int, int> table[1001];
void dijkstra(int n, int departure, int arrival);
void retrace(int departure, int arrival);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, departure, arrival;
cin >> n >> m;
for (int i=1; i<n+1; i++) {
for (int j=1; j<n+1; j++) {
graph[i][j] = INT_MAX;
}
}
for (int i=0; i<m; i++) {
int start, end, weight;
cin >> start >> end >> weight;
graph[start][end] = min(graph[start][end], weight);
}
cin >> departure >> arrival;
dijkstra(n, departure, arrival);
cout << table[arrival].first << "\n";
retrace(departure, arrival);
return 0;
}
void dijkstra(int n, int departure, int arrival) {
bool visit[1001] = {false,};
for (int i=1; i<n+1; i++) {
table[i].first = INT_MAX;
if (i == departure) table[i].first = 0;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
pq.emplace(departure, 0);
for (int i=0; i<n-1; i++) {
if (pq.empty()) break;
pair<int, int> curr = pq.top();
pq.pop();
visit[curr.first] = true;
if (curr.second > table[curr.first].first) continue;
for (auto& j : graph[curr.first]) {
if (j.second != INT_MAX) {
if (curr.second + j.second < table[j.first].first) {
table[j.first].first = curr.second + j.second;
table[j.first].second = curr.first;
pq.emplace(j.first, table[j.first].first);
}
}
}
}
}
void retrace(int departure, int arrival) {
int curr = arrival;
stack<int> s;
while (curr != departure) {
s.push(curr);
curr = table[curr].second;
}
s.push(curr);
cout << s.size() << "\n";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
계속 시간 초과가 뜨길래 머리가 어지럽고 속이 무척 답답했다. 어쨌든 해결이 되어서 정말 다행인 것 같다. CLASS 4를 마스터하기까지 4문제 정도 남았는데, 어떤 역경이 나를 기다리고 있을지 조금은 걱정된다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/11779